import java.util.ArrayList;

/**
 * @version Create on 2012-11-13
 * @author Yinzi Chen
 */

public class NQueens {
	ArrayList<String[]> res;
	boolean[][] map;
	int size, cnt;

	public boolean check(int idx) {
		int p = idx / size, q = idx % size;
		for (int i = 0; i < idx; ++i) {
			int x = i / size, y = i % size;
			if (map[x][y]
					&& (x == p || y == q || Math.abs(p - x) == Math.abs(q - y))) {
				return false;
			}
		}
		return true;
	}

	public void search(int idx) {
		if (idx == size * size) {
			if (cnt != size)
				return;
			String[] s = new String[size];
			for (int i = 0; i < size; ++i) {
				s[i] = "";
				for (int j = 0; j < size; ++j) {
					s[i] += map[i][j] ? "Q" : ".";
				}
			}
			res.add(s);
			return;
		}
		if (idx / size > cnt)
			return;
		int p = idx / size, q = idx % size;
		if (check(idx)) {
			cnt++;
			map[p][q] = true;
			search(idx + 1);
			map[p][q] = false;
			cnt--;
		}
		search(idx + 1);
	}

	public ArrayList<String[]> solveNQueens(int n) {
		res = new ArrayList<String[]>();
		map = new boolean[n][n];
		size = n;
		cnt = 0;
		search(0);
		return res;
	}

	public static void main(String[] args) {
		NQueens a = new NQueens();
		a.solveNQueens(10);
	}

}
